package com.demo.java.OD201_250.OD206;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【高效的任务规划】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145906329
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();  // 输入任务的组数
        while (m-- > 0) {
            int n = scanner.nextInt();  // 任务数量
            int[][] jobs = new int[n][2];  // 记录任务的工作量和机器效率
            for (int i = 0; i < n; i++) {
                jobs[i] = new int[]{scanner.nextInt(), scanner.nextInt()};
            }
            System.out.println(solve(jobs));  // 计算并输出每组任务完成的最短时间
        }
        scanner.close();
    }

    private static int solve(int[][] jobs) {
        // 按照任务的工作量从大到小排序
        Arrays.sort(jobs, (job1, job2) -> job2[1] - job1[1]);

        int time = 0, remaining = 0;
        // 遍历每个任务，按照最优方式进行分配
        for (int[] job : jobs) {
            time += job[0];  // 累加任务的工作量
            remaining = Math.max(remaining - job[0], job[1]);  // 更新剩余的最大时间
        }
        return time + remaining;  // 返回完成任务所需的最短时间
    }
}